//
// Created by Administrator on 2022/2/5.
//

#ifndef CPP_LEARNING_LEETCODE987_H
#define CPP_LEARNING_LEETCODE987_H
#include "treenode.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
class Solution987 {
public:
    void preOrder(TreeNode* node, int row, int col, map<int, map<int, vector<int>>>& colMap, map<int, vector<int>>& colList, set<int>& colSet){
        if(node == nullptr)  return;
        colMap[col][row].push_back(node->val);
        colList[col].push_back(row);
        colSet.insert(col);

        preOrder(node->left, row+1, col-1, colMap, colList,colSet);
        preOrder(node->right, row+1, col+1, colMap, colList,colSet);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        // col vector(row)
        map<int, vector<int>> colList;
        map<int, map<int, vector<int>>> colMap;
        set<int> colSet;
        preOrder(root, 0, 0, colMap, colList, colSet);

        vector<vector<int>> result;
        for(auto& col_val : colSet){
            vector<int> & row_list = colList[col_val];
            vector<int>::iterator it = unique (row_list.begin(), row_list.end() );
            row_list.erase (it, row_list.end() );//这里就是把后面藏起来的重复元素删除了

            sort(row_list.begin(), row_list.end());

            vector<int> temp;
            for(auto& row_val : row_list){
                vector<int>& col_row_list = colMap[col_val][row_val];
                sort(col_row_list.begin(), col_row_list.end());
                for(auto& val:col_row_list){
                    temp.push_back(val);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};


void test987(){
    TreeNode* node1 = new TreeNode(1);
    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node6 = new TreeNode(6);
    TreeNode* node7 = new TreeNode(7);


    node1->left = node2;
    node1->right = node3;

    node2->left = node4;
    node2->right = node5;

    node3->left = node6;
    node3->right = node7;

    Solution987 s;
    vector<vector<int>> num = s.verticalTraversal(node1);

}
#endif //CPP_LEARNING_LEETCODE987_H
